package com.mystudy.dataStructure.queue;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class LoopQueue<E> implements Queue<E> {
    private static final Logger LOGGER = LoggerFactory.getLogger(LoopQueue.class);
    
    private E[] data;
    private int front;//队首所在索引
    private int tail;//队尾所在索引,最后一个数据后面的单位
    private int size;


    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];//循环队列要有意的浪费一个空间，所以要加1
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return data.length - 1;//还是有一个会被浪费掉，所以真正能够承载的容量要减一
    }

    @Override
    public void enqueue(E e) {
        //队列满的时候要扩容
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail+1) % data.length;
        System.out.println("tail:"+tail);
        size++;

    }

    private void resize(int capacity) {
        E[] newData = (E[]) new Object[capacity + 1];
        for (int i = 0; i < size; i++) {
            //此时newData的0应该是data的front才对，所以应该有front的偏移量
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }


    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("cannot dequeue from empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        LOGGER.debug("front = [ {} ]",front);
        size--;
        if (size == getCapacity() / 4) {
            resize(getCapacity() / 2);//缩容
        }
        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("cannot dequeue from empty queue");
        }

        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }


    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append(String.format("LoopQueue: size = %d , capacity = %d \n", size, data.length));
        result.append("front[");
        //与动态数组完全不同的遍历方式
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            result.append(data[i]);
            if ((i+1)%data.length != tail) {
                result.append(", ");
            }
        }
        result.append("] tail");
        return result.toString();
    }
}
